package com.gxc.queue;

import java.util.*;

/**
 * 项目组共有N个开发人员，项目经理接到了M个独立的需求，每个需求的工作量不同，且每个需求只能由一个开发人员独立完成，不能多人合作。
 *
 * 假定各个需求直接无任何先后依赖关系，请设计算法帮助项目经理进行工作安排，使整个项目能用最少的时间交付。
 *
 * 输入描述
 * 第一行输入为M个需求的工作量，单位为天，用逗号隔开。 例如：X1 X2 X3 … Xm 表示共有M个需求，每个需求的工作量分别为X1天，X2天…Xm天。其中0<M<30；0<Xm<200 第二行输入为项目组人员数量N 例如： 5 表示共有5名员工，其中0<N<10.
 *
 * 输出描述
 * 最快完成所有工作的天数 例如： 25 表示最短需要25天能完成所有工作。
 */
public class MinTime {

    // 判断是否满足要求
    public static boolean judge(List<Integer> ans, int personNum, int target, int index, int[] load) {
        if (index < 0) {
            return true;
        }
        for (int i = 0; i < personNum; i++) {
            // 剪枝
            if (i > 0 && load[i] == load[i - 1]) {
                continue;
            }

            // 递归回溯
            if (load[i] + ans.get(index) <= target) {
                load[i] += ans.get(index);
                if (judge(ans, personNum, target, index - 1, load)) {
                    return true;
                }
                load[i] -= ans.get(index);
            }
            // 剪枝：如果当前人是第一个任务都没分配过的，直接跳出，避免不必要尝试
            if (load[i] == 0) {
                break;
            }
        }
        return false;
    }

    // 二分 + 递归回溯
    public static int solve(List<Integer> ans, int personNum) {
        int sum = ans.stream().mapToInt(Integer::intValue).sum();
        int left = 0, right = sum;

        while (left < right) {
            int target = (left + right) / 2;
            int[] load = new int[personNum];

            if (judge(ans, personNum, target, ans.size() - 1, load)) {
                right = target;
            } else {
                left = target + 1;
            }
        }
        return left;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String s = scanner.nextLine();
        int personNum = scanner.nextInt();
        scanner.close();

        String[] tmp = s.split(" ");
        List<Integer> ans = new ArrayList<>();
        for (String num : tmp) {
            ans.add(Integer.parseInt(num));
        }

        // 从小到大排序
        Collections.sort(ans);
        int res = solve(ans, personNum);
        System.out.println(res);
    }
}
